#include "avlTree.h"
#include <stdio.h>

AvlTree MakeEmpty(AvlTree T)
{
    if (T != NULL)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        //先序遍历释放整个二叉树
        free(T);
    }
    return NULL;
}
Position Find(ElementType X, AvlTree T)
{
    if (T == NULL)
    {
        return NULL;
    }

    if (X < T->Element)
    {
        //使用尾递归，这种递归方式很容易能被改写为循环或者goto。但是为了方便，我们将其写为尾递归的方式。
        //编译时，指定优化尾递归来防止递归可能造成的栈溢出。
        return Find(X, T->Left);
    }
    else if (X > T->Element)
    {
        return Find(X, T->Right);
    }
    else
    {
        return T;
    }
}
Position FindMin(AvlTree T)
{
    if (T == NULL)
    {
        return NULL;
    }
    else if (T->Left == NULL)
    {
        return T;
    }
    else
    {
        return FindMin(T->Left);
    }
}
Position FindMax(AvlTree T)
{
    //我们可以轻松地将尾递归改写为循环
    if (T != NULL)
    {
        while (T->Right != NULL)
        {
            T = T->Right;
        }
    }
    return T;
}

static int Height(Position P)
{
    if (P == NULL)
    {
        return -1;
    }
    else
    {
        return P->Height;
    }
}

static int Max(ElementType x, ElementType y)
{
    return x > y ? x : y;
}

//把左边的树变成右边的树，并返回指向新根的指针
//This function can be called only if k2 has a left child
//Perform a rotate
static Position SingleRotateWithLeft(Position K2)
{
    Position K1;
    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
    K1->Height = Max(Height(K1->Left), K2->Height) + 1;

    return K1;
}

static Position SingleRotateWithRight(Position K2)
{
    Position K1;
    K1 = K2->Right;
    K2->Right = K1->Left;
    K1->Left = K2;

    K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
    K1->Height = Max(Height(K1->Right), K2->Height) + 1;
    return K1;
}

static Position DoubleRotateWithLeft(Position K3)
{
    K3->Left = SingleRotateWithRight(K3->Left);
    return SingleRotateWithLeft(K3);
}

static Position DoubleRotateWithRight(Position K3)
{
    K3->Right = SingleRotateWithLeft(K3->Right);
    return SingleRotateWithRight(K3);
}

AvlTree Insert(ElementType X, AvlTree T)
{
    if (T == NULL)
    {
        //insert
        T = malloc(sizeof(struct AvlNode));
        if (T == NULL)
        {
            printf("malloc error\n");
            return NULL;
        }
        else
        {
            T->Element = X;
            T->Height = 0;
            T->Left = T->Right = NULL;
        }
    }
    else if (X < T->Element)
    {
        T->Left = Insert(X, T->Left);
        if (Height(T->Left) - Height(T->Right) == 2)
        {
            if (X < T->Left->Element)
            {
                T = SingleRotateWithLeft(T);
            }
            else
            {
                T = DoubleRotateWithLeft(T);
            }
        }
    }
    else if (X > T->Element)
    {
        T->Right = Insert(X, T->Right);
        if (Height(T->Right) - Height(T->Left) == 2)
        {
            if (X > T->Right->Element)
            {
                T = SingleRotateWithRight(T);
            }
            else
            {
                T = DoubleRotateWithRight(T);
            }
        }
    }
    T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
    return T;
}

static void printTab(AvlTree T, int tabLevel)
{
    int i = 0;

    if (T != NULL)
    {
        for (i = 0; i < tabLevel; i++)
        {
            printf("    ");
        }
        printf("%d:%d\n", T->Element, T->Height);
        printTab(T->Left, tabLevel + 1);
        printTab(T->Right, tabLevel + 1);
    }
}

void Print(AvlTree T)
{
    printTab(T, 0);
}